package com.laotang.第_4_章_哈希表.力扣_1_两数之和;

import java.util.Arrays;

public class _1_TwoSum3 {

    static class Pair {
        int num;
        int index;

        Pair(int num, int index) {
            this.num = num;
            this.index = index;
        }
    }

    // 二分查找
    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(n)
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Pair[] pairs = new Pair[n];
        for (int i = 0; i < n; i++) {
            pairs[i] = new Pair(nums[i], i);
        }

        Arrays.sort(pairs, (p1, p2) -> {return p1.num - p2.num;});

        for (int i = 0; i < n; i++) {
            int num = target - pairs[i].num;
            int index = binarySearch(pairs, i + 1, n - 1, num);
            if (index != -1) return new int[]{pairs[i].index, index};
        }

        return new int[0];
    }

    int binarySearch(Pair[] pairs, int left, int right, int target) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (pairs[mid].num == target) {
                return pairs[mid].index;
            } else if (pairs[mid].num < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
